//题目:
// 给你一个整数数组 arr 和一个整数 difference，
// 请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
// 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

// 示例 1：
// 输入：arr = [1,2,3,4], difference = 1
// 输出：4
// 解释：最长的等差子序列是 [1,2,3,4]。

// 示例 2：
// 输入：arr = [1,3,5,7], difference = 1
// 输出：1
// 解释：最长的等差子序列是任意单个元素。

// 示例 3：
// 输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
// 输出：4
// 解释：最长的等差子序列是 [7,5,3,1]。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        //1.创建dp表————dp[i]表示以 nums[i] 为结尾的 最长定差子序列长度
        // vector<int> dp(arr.size(),1);
        int hash[400001]={0};
        //2.初始化
        hash[20000+arr[0]]=1;
        //3.填表————动态转移方程：dp[i]=arr[i]-arr[j]==difference?dp[j]+1:1
        for(int i=1;i<arr.size();i++)          
            hash[20000+arr[i]]=hash[20000+arr[i]-difference]+1;
        //4.确定返回值
        int ret=1;
        for(int i=0;i<arr.size();i++)
            ret=max(ret,hash[20000+arr[i]]);
        return ret;
    }
};